package week3;

import java.util.*;

/**
 *
 * 47. 全排列 II
 * https://leetcode-cn.com/problems/permutations-ii/
 *
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：2 ms, 在所有 Java 提交中击败了56.12% 的用户
 * 内存消耗：39 MB, 在所有 Java 提交中击败了69.70% 的用户
 *
 *
 */
public class Week3PermutationsII {

    public List<List<Integer>> permuteUnique(int[] nums) {
        int length = nums.length;
        List<List<Integer>> permuteList = new ArrayList<List<Integer>>();
        if (length == 0) {
            // 终止
            return permuteList;
        }
        Arrays.sort(nums); // 保持数组有序
        boolean[] used = new boolean[length];
        Deque<Integer> path = new ArrayDeque<Integer>(length);
        dfs(nums, length, 0, used, path, permuteList);

        return permuteList;
    }

    public void dfs(int[] nums, int length, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> list) {
        if (depth == length) {
            // 终止
            list.add(new ArrayList<Integer>(path));
            return;
        }

        for(int size = 0; size < length; size++) {
            if(used[size]) {
                // 忽略使用过的
                continue;
            }

            if(size > 0 && nums[size] == nums[size - 1] && !used[size - 1]) {
                // 忽略 相邻值相同的
                continue;
            }
            path.addLast(nums[size]);
            used[size] = true;
            dfs(nums, length, depth + 1, used, path, list);
            used[size] = false;
            path.removeLast();

        }
    }


}
